#include<bits/stdc++.h>
using namespace std;
int a[200001],b[1000001],c[200001],d[200001],e[200001],f[200001],g[1000001];
long long q[101][101][101],q1[2001][2001];
set<int>s;
int main(){
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    int t;
    scanf("%d",&t);
    while(t--){
        memset(b,0,sizeof(b));
        memset(d,0,sizeof(d));
        memset(e,0,sizeof(e));
        memset(g,0,sizeof(g));
        memset(q1,0,sizeof(q1));
        s.clear();
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            c[i]=b[a[i]];
            b[a[i]]=i;
            f[i]=f[i-1];
            if(a[i]==a[i-1])
                f[i]+=a[i];
            g[a[i]]++;
        }
        long long h=0;
        int h1=0;
        for(int i=1;i<=1000000;i++){
            if(1ll*(g[i]-1)*i>h){
                h=1ll*(g[i]-1)*i;
                h1=i;
            }
        }
        int h2=0;
        for(int i=1;i<=n;i++){
            if(a[i]==h2)
                h+=a[i];
            if(a[i]!=h1)
                h2=a[i];
        }
        int q=0,w=0;
        for(int i=1;i<=n;i++){
            d[i]=d[i-1];
            if(c[i])
                d[i]=max(d[i],d[c[i]]+a[i]);
        }
        int g=0;
        for(int i=1;i<=n;i++)
            g=max(g,d[i]);
        for(int i=1;i<=n;i++)
            for(int j=0;j<i;j++)
                q1[i][j]=max(q1[i-1][j],q1[j][j]+(a[i]==a[j]?a[i]:0)+f[i-1]-f[j]);
        long long qq=0;
        for(int i=0;i<=n;i++)
            qq=max(qq,q1[n][i]);
        printf("%lld\n",qq);
    }
    return 0;
}